#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// https://leetcode.cn/problems/subsets-ii/description/?envType=problem-list-v2&envId=z8Em6vKo
// 90. 子集 II

class Solution
{
public:
    void recursionTry(vector<vector<int>> &ans, vector<int> &target, int curIndex, int size, vector<int> &curSet)
    {
        if (curIndex == target.size())
        {
            vector<int> temp(curSet.begin(), curSet.begin() + size);
            ans.push_back(temp);
        }
        else
        {
            // 同种数的个数
            int nextNumIndex = curIndex;
            while (nextNumIndex < target.size() && target[nextNumIndex] == target[curIndex])
            {
                ++nextNumIndex;
            }
            // 不选此数
            recursionTry(ans, target, nextNumIndex, size, curSet);
            // 选分支
            for (int i = 1; i <= nextNumIndex - curIndex; i++){
                curSet[size  + i - 1] = target[curIndex];
                recursionTry(ans, target, nextNumIndex, size + i, curSet);
            }
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        vector<int> temp(nums.size());
        recursionTry(ans, nums, 0, 0, temp);
        return ans;
    }
};

int main()
{
    Solution solution{};
    vector<int> nums{1, 2};
    solution.subsetsWithDup(nums);
    return 0;
}